package hotLeetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class H39Leetcode {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, res, path, 0,0);
        return res;
    }


    private void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> path, int sum, int idx) {

        //结束条件
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }


        for (int i = idx; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            sum += candidates[i];
            path.add(candidates[i]);
            //递归
            dfs(candidates, target, res, path, sum,i);
            //回溯
            path.remove(path.size() - 1);
            sum -= candidates[i];


        }

    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        H39Leetcode h39Leetcode = new H39Leetcode();
        System.out.println(h39Leetcode.combinationSum(candidates, 7));

    }
}
